The present invention relates to a binary data compression and expansion processing apparatus which can expand binary data at high speed, and particularly, can parallel-decode, in a pipeline manner, binary data compressed by the M.sup.2 R method.
As a method for compressing and expanding binary data, coding methods, such as the MH method, the MR method, and the M.sup.2 R method, recommended by the CCITT, are internationally standardized, and are widely adopted. Among the three coding methods, i.e., the MH, MR, and M.sup.2 R methods, the M.sup.2 R method has the highest image compression efficiency.
The M.sup.2 R method is well known as a coding method for Group IV facsimile systems. In this method,
a. an End-Of-Line (EOL) code is omitted, PA0 b. a k parameter is set to be infinite, and PA0 c. all the bits of a reference line at the beginning of a page represent white pixels. PA0 a. decoding processing of code PA0 b. generation processing of image data for the decoded code Therefore, decoding and generation processing can be parallel-performed by separate hardware arrangements. In such arrangements, while a code is expanded, the next code is decoded, and the entire processing can be then pipelined. When binary data encoded by MH and MR methods is expanded, there is no problem in the advanced processing. However, the M.sup.2 R method has the following problems.
With these assumptions, a data compression ratio can be improved over that of the MR method. If a transmission error, if any, occurs, the error is sequentially transmitted to subsequent scanning lines as a principal problem. In order to prevent this, one-dimensional coding scanning lines are inserted in compression processing. The k parameter is the number of two-dimensional coding scanning lines between these one-dimensional coding scanning lines.
A conventional binary data compression and expansion processing apparatus has been realized in software, using a general-purpose microcomputer in order to perform expansion processing of encoded data according to these methods. In this processing, there is no problem when such an apparatus is applied to a facsimile system whose data transmission rate is limited to 9600 bps. However, when the conventional apparatus is used to display image data on work stations of a computer system, a good man-machine interface, for example, a page response time of 1/2 sec or less, cannot be achieved. Therefore, when the sequential expansion processing is executed in accordance with the M.sup.2 R method, the operating speed is considerably reduced, when compared with the MH method.
One cause of the above problem lies in the processing method of the entire system. More specifically, in a conventional system, decoding is performed in a bit serial manner. In order to solve the problem, parallel processing, advanced processing, and pipeline processing are widely utilized. The binary image data expansion processing can be apparently divided into:
In all the MH, MR, and M.sup.2 R methods, the starting run of each line is always a white run and must be decoded to be white pixels. In the case of the MH and MR methods, an EOL code is used. Therefore, a decoding processing section which performs the advanced processing can detect the beginning of the next line due to the presence of an EOL code regardless of the progress of generation processing by a generation processing section.
However, since there is no EOL code in the M.sup.2 R method, the beginning of the next line can only be detected when the generation processing section develops each code and reaches an end of line. Therefore, if the beginning of the next line is indeterminate, it cannot be determined if the color of this portion is forcibly determined as white.
As a result, a decoding operation of a horizontal mode using separate code tables for a white run and a black run cannot be started in an advanced manner. More specifically, in the expansion processing of the M.sup.2 R method of a conventional apparatus, the advanced processing cannot be effectively performed.
As described above, the conventional apparatus has problems in a processing rate, a capability of general purpose use.